package com.zhupf.part4;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhupf
 * @date 2023年10月31日 11:30
 * @Description 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
 * <p>
 * 子数组是数组中元素的连续非空序列。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 */
public class SubarraySum {


    public static void main(String[] args) {

        int[] nums = {1,1,1};
        int k = 2;
        System.out.println(subarraySum2(nums, k));

    }

    /**
     * 前缀和  时间复杂度（ o(n2) ）
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum(int[] nums, int k) {
        int result = 0;
        int[] prefSum = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            prefSum[i] = i == 0 ? nums[i] : nums[i] + prefSum[i - 1];
        }
        int idx = prefSum.length - 1;
        while (idx >= 0) {
            int i = 0;
            result = prefSum[idx] == k ? result + 1 : result;
            while (idx > i) {
                if ((prefSum[idx] - prefSum[i++]) == k) {
                    result++;
                }
            }
            idx--;
        }
        return result;
    }


    /**
     * 前缀和 + 哈希
     *
     * @param nums
     * @param k
     * @return
     */
    public static int subarraySum2(int[] nums, int k) {
        int result = 0;
        int[] prefSum = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            prefSum[i] = i == 0 ? nums[i] : nums[i] + prefSum[i - 1];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < prefSum.length; i++) {
            result = prefSum[i] == k ? result +1 : result;
            Integer integer = map.get(prefSum[i] - k);
            if(integer != null){
                result = result + integer;
            }
            map.put(prefSum[i], map.get(prefSum[i]) == null ? 1 : map.get(prefSum[i]) + 1);
        }
        return result;
    }


}
